It may be recalled that the methods called “wavelet encoding methods” are used to represent a mesh as a succession of details added to a base mesh. The general theory of this technique is described for example in M. Lounsbery, T. DeRose and J. Warren, “Multiresolution Analysis for Surfaces of Arbitrary Topological Type” (ACM Transaction on Graphics, Vol. 16, No. 1, pp. 34-73, January 1997).
The general principle of this technique consists in developing homeomorphism between an object to be encoded (such as a 3D mesh for example) and a simple mesh (more generally called in a “base mesh”) in a base of particular functions called second-generation wavelets.
In this technique, a mesh is therefore represented by a sequence of coefficients that correspond to the coordinates in a wavelet base of a parametrization of this mesh by a simple polyhedron.
Thus, an object encoded according to this technique takes the form of the union of the following two elements:                the base mesh, which generally comprises few facets, and represents a coarse version of the object to be encoded;        the wavelet coefficients, which are triplets of real values assigned simultaneously to a precise zone of the base mesh and to a given level of subdivision of this mesh. These wavelet coefficients represent refinements to be made to the zone with which they are associated to converge towards the geometry of the initial object.        
To enable the reconstruction of a representation of the encoded object on a display terminal, it is necessary to transmit on the one hand the base mesh and on the other hand the associated wavelet coefficients to this terminal.
There are several known techniques for the encoding of wavelet coefficients for transmission to a display terminal. Among these, the “zero-tree” encoding technique gives results that are particularly useful in terms of compression. Such a technique consists in describing an order of encoding of the wavelet coefficients which is predetermined and known in advance to the sender and receiver terminals (for example a server and a customer's display terminal). It can therefore be used in the transmission of the wavelet coefficients to prevent the transmission of information on sets of coefficients that are insignificant for the encoding of the object considered. The elimination of the insignificant coefficients enables a satisfactory level of compression to be achieved.
The techniques of “zero-tree” encoding make advantageous use of the fact that, at the finest levels of detail, the wavelet coefficients have smaller amplitude than wavelet coefficients associated with the coarser levels of subdivision.
Such zero-tree encoding operations are generally coupled with a “bitplane encoding” used, during the transmission of the coefficients, to transmit the most significant bits of each coefficient first. The requirements of progressivity of the encoding technique are thus met.
For a more detailed description of the zero-tree techniques, reference could be made to the articles by Jerome M. Shapiro, “Embedded Image Coding Using Zerotrees of Wavelet Coefficients” (IEEE Trans. Sig. Proc. 41(12), December 1993) and by A. Said, W. A. Pearlman, “A New, Fast, and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees” (IEEE Trans. Circ. System. For Video Tech., 6(3), June 1996).
As explained in this article by A. Said and W. A. Pearlman, the zero-tree encoding/decoding algorithm, also called the SPIHT (“Set Partitioning in Hierarchical Trees”) algorithm is used to obtain an overall binary representation of the set of wavelet coefficients, which contains sorting bits and bits coming from a binary representation of the coefficients. Applied to 2D wavelet image encoding, this SPIHT algorithm, during the decoding, reconstructs the hierarchy of the pixels of the image and distributes the bits as and when they are extracted from the bitstream.
The SPIHT algorithm, initially developed for the encoding of 2D images, has recently been applied to second-generation wavelet coefficients as described in A. Khodakovsky, P. Schröder and W. Sweldens, “Progressive Geometry Compression” (SIGGRAPH 2000 proceedings) and F. Moran and N. Garcia, “Hierarchical Coding of 3D Models with Subdivision Surfaces” (IEEE ICIP 2000 Proceedings).
Thus, for second-generation wavelets, a bitstream is obtained with the same type of format as in the case of the classic wavelets used for 2D image encoding.
As presented initially in the context of classic wavelet encoding of 2D images by A. Said and W. A. Pearlman in the above-mentioned article, the SPIHT algorithm necessitates the holding in memory of a table of the size of the image to be rebuilt, i.e. containing as many elements as wavelet coefficients. The inventors of the present patent application have established the fact that its adaptation to second-generation wavelets preserves this requirement; thus, in the case of partial or adaptive data transmission, the decoding of some wavelet coefficients necessitates the storage in memory of the entire hierarchy of the mesh associated with a 3D object or the multimedia scene to be rebuilt.
The SPIHT algorithm, applied to second-generation wavelet-encoded 3D objects, therefore has severe limits when it is sought to carry out an adaptive decoding of the transmitted object.
Now, an adapted decoding of this kind proves to be particularly promising for many applications, for example adaptive streaming of geographical terrains. In such an application, a user makes an interactive visit to a virtual geographical region, transmitted by a server on a communications network, such as the Internet for example. Depending on the region visited by the user, the server sends the restitution terminal only data that can be seen by this terminal. The relevance of the data is determined especially according to the user's viewpoint, his position in the virtual scene or a specific request made to the server by this user, etc.
A first drawback of the prior art SPIHT algorithm, in the context of second-generation wavelet-encoded 3D objects, therefore lies in the need to keep the totality of the zero-tree hierarchy stored in memory. Indeed, a partial decoding of the bitstream calls for the creation in memory of the totality of the hierarchical structure, even when a part of this structure is designed to contain only zeros, only a part of the scene encoded in the bitstream being visible to the user or of interest to the user.
Another drawback of the prior art SPIHT algorithm, in the context of second-generation wavelet-encoding of 3D objects, is of an algorithmic nature.
Indeed, in an adaptive transmission, the following are the two phases of the reconstruction of a 3D scene or 3D object from a bitstream, to obtain a 3D mesh:                the zero-tree decoding which, from the data bitstream, produces the wavelet coefficients;        and an inverse wavelet transform which, on the basis of the wavelet coefficients extracted from the bitstream, produces a 3D mesh.        
Classically, and as shown in FIG. 1, the wavelet coefficients 15, after zero-tree decoding, are stored in a cache 10, accompanied by a piece of locating information, expressed for example in the form of barycentric coordinates (F, A, B, C), where F is a facet of the base mesh on which the vertex indexing the wavelet coefficient is located and where A, B and C are barycentric coordinates of the vertex on the facet F. This locating information enables the reconstruction process 11 to integrate the corresponding wavelet coefficients in the 3D representation 12 independently.
One drawback of the prior art SPIHT technique for 3D objects therefore is that the reconstruction process 11 depends on the stopping of the decoding process 13. In other words, so long as the totality of the bitstream 14 has not been decoded 13, it is not possible to carry out an adaptive reconstruction of only that portion of the 3D object which is likely to interest the user.
A SPIHT technique of this kind therefore does not provide for an adaptive real-time viewing of 3D objects or scenes.